package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-falling-path-sum/description/
 * @create 2025/8/31 14:35
 * @since JDK17
 */

public class Solution34 {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m];
        for (int i = 0; i < m; i++) {
            dp[0][i] = matrix[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0, min; j < m; j++) {
                min = Integer.MAX_VALUE;
                for (int k = j - 1 < 0 ? 0 : j - 1; k < m && k <= j + 1; k++) {
                    min = Math.min(min, dp[i - 1][j]);
                }
                dp[i][j] = matrix[i][j] + min;
            }
        }
        return Arrays.stream(dp[n - 1]).min().getAsInt();
    }
}
